/*
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

执行用时 :24 ms, 在所有 C++ 提交中击败了72.29%的用户
内存消耗 :8 MB, 在所有 C++ 提交中击败了100.00%的用户

复杂度分析：
只遍历了一遍，所以时间复杂度是O(n),开辟了新的链表,空间复杂度是O(n)

*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        int cf = 0;
        while (l1 || l2 || cf != 0) {
            int l1Val = l1?l1->val:0;	//三目运算符别搞混
            int l2Val = l2?l2->val:0;
            int sumVal = l1Val + l2Val +cf;
            cf = sumVal/10;
            ListNode* tmp = new ListNode(sumVal%10);
            cur->next = tmp;
            cur = tmp;
            if (l1) {		//l1不空时指向下一个
                l1 = l1->next;	
            }
            if (l2) {
                l2 = l2->next;
            }
        } 
        return dummy->next;
    }
};
void print(ListNode* head){
	ListNode* cur = head;
	while(cur){
		cout<<cur->val<<"  ";
		cur = cur->next;
	}
	cout<<endl;
}
int main(int argc, char const* argv[]){
	int a1[3] = {2,5,9};
	int a2[4] = {8,0,0,9};
	ListNode* dm1 = new ListNode(0);
	ListNode* dm2 = new ListNode(0);
	ListNode* c1 = dm1;
	ListNode* c2 = dm2;
	for (int i = 0 ;i < 3;i++) {
		ListNode* tmp = new ListNode(a1[i]);
		c1->next = tmp;
		c1 = tmp;
	}
	for (int i = 0;i < 4;i++) {
		ListNode* tmp = new ListNode(a2[i]);
		c2->next = tmp;
		c2 = tmp;
	}
	Solution s;
	ListNode* ans  = s.addTwoNumbers(dm1->next,dm2->next);
	print(ans);
	return 0;
}
